{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Naming a Company"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #string #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #字符串 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distinctNames"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #公司命名"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>ideas</code> 表示在公司命名过程中使用的名字列表。公司命名流程如下：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>从 <code>ideas</code> 中选择 2 个 <strong>不同</strong> 名字，称为 <code>idea<sub>A</sub></code> 和 <code>idea<sub>B</sub></code> 。</li>\n",
    "\t<li>交换 <code>idea<sub>A</sub></code> 和 <code>idea<sub>B</sub></code> 的首字母。</li>\n",
    "\t<li>如果得到的两个新名字 <strong>都</strong> 不在 <code>ideas</code> 中，那么 <code>idea<sub>A</sub> idea<sub>B</sub></code>（<strong>串联</strong> <code>idea<sub>A</sub></code> 和 <code>idea<sub>B</sub></code> ，中间用一个空格分隔）是一个有效的公司名字。</li>\n",
    "\t<li>否则，不是一个有效的名字。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回 <strong>不同</strong> 且有效的公司名字的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>ideas = [\"coffee\",\"donuts\",\"time\",\"toffee\"]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>下面列出一些有效的选择方案：\n",
    "- (\"coffee\", \"donuts\")：对应的公司名字是 \"doffee conuts\" 。\n",
    "- (\"donuts\", \"coffee\")：对应的公司名字是 \"conuts doffee\" 。\n",
    "- (\"donuts\", \"time\")：对应的公司名字是 \"tonuts dime\" 。\n",
    "- (\"donuts\", \"toffee\")：对应的公司名字是 \"tonuts doffee\" 。\n",
    "- (\"time\", \"donuts\")：对应的公司名字是 \"dime tonuts\" 。\n",
    "- (\"toffee\", \"donuts\")：对应的公司名字是 \"doffee tonuts\" 。\n",
    "因此，总共有 6 个不同的公司名字。\n",
    "\n",
    "下面列出一些无效的选择方案：\n",
    "- (\"coffee\", \"time\")：在原数组中存在交换后形成的名字 \"toffee\" 。\n",
    "- (\"time\", \"toffee\")：在原数组中存在交换后形成的两个名字。\n",
    "- (\"coffee\", \"toffee\")：在原数组中存在交换后形成的两个名字。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>ideas = [\"lack\",\"back\"]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在有效的选择方案。因此，返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= ideas.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= ideas[i].length &lt;= 10</code></li>\n",
    "\t<li><code>ideas[i]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>ideas</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [naming-a-company](https://leetcode.cn/problems/naming-a-company/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [naming-a-company](https://leetcode.cn/problems/naming-a-company/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"coffee\",\"donuts\",\"time\",\"toffee\"]', '[\"lack\",\"back\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = collections.defaultdict(set)\n",
    "        for idea in ideas:\n",
    "            value = hash(idea[1:])\n",
    "            group[idea[0]].add(value)\n",
    "        result = 0\n",
    "        for a, b in itertools.combinations(group, 2):\n",
    "            ga = group[a]\n",
    "            gb = group[b]\n",
    "            overlap = len(ga & gb)\n",
    "            result += (len(ga) - overlap) * (len(gb) - overlap)\n",
    "        return result << 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        cnt=collections.defaultdict(list)\n",
    "        for x in ideas:\n",
    "            head=x[0]\n",
    "            tail=x[1:]\n",
    "            if tail not in cnt[head]:\n",
    "                cnt[head].append(tail)\n",
    "            ans=0\n",
    "       # print(cnt)\n",
    "        for i in range(ord(\"a\"),ord(\"z\")):\n",
    "            for j in range(i+1,ord(\"z\")+1):\n",
    "                # print(chr(i),chr(j))\n",
    "                len1=len(cnt[chr(i)])\n",
    "                len2=len(cnt[chr(j)])\n",
    "                len3=len(set(cnt[chr(i)]+cnt[chr(j)]))\n",
    "                ans+=(len3-len1)*(len3-len2)\n",
    "               # print(ans)\n",
    "        return ans*2\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        last_dic = {}\n",
    "        first_dic = {}\n",
    "        last_count = {}\n",
    "        first_count = {}\n",
    "        for it in ideas:\n",
    "            if it[0] not in first_dic:\n",
    "                first_dic[it[0]] = []\n",
    "                first_count[it[0]] = 0\n",
    "            first_dic[it[0]].append(it[1:])\n",
    "            first_count[it[0]] += 1\n",
    "            '''\n",
    "            if it[1:] not in last_dic:\n",
    "                last_dic[it[1:]] = 0\n",
    "                last_count[it[1:]] = 0\n",
    "            last_dic[it[1:]] += 1<<(ord(it[0])-ord('a'))\n",
    "            last_count[it[1:]] += 1\n",
    "            '''\n",
    "        num = 0\n",
    "        key = list(first_dic.keys())\n",
    "        for i,k in enumerate(key):\n",
    "            for t in key[i+1:]:\n",
    "                '''\n",
    "                tmp = last_dic[k]&last_dic[t]\n",
    "                tmp_count = 0\n",
    "                while tmp:\n",
    "                    tmp = tmp & (tmp - 1)\n",
    "                    tmp_count += 1\n",
    "                #tmp = list(map(lambda e,f:e*f, last_dic[k],last_dic[t]))\n",
    "                '''\n",
    "                tmp = list(set(first_dic[k]).intersection(set(first_dic[t])))\n",
    "                tmp_count = len(tmp)\n",
    "                num = num + 2 * (first_count[k] - tmp_count) *  (first_count[t] - tmp_count)      \n",
    "        '''\n",
    "        for it in ideas:\n",
    "            a = it[0]\n",
    "            b = it[1:]\n",
    "            for i in first_dic.keys():\n",
    "                if i in last_dic[b]:\n",
    "                    continue\n",
    "                for k in first_dic[i]:\n",
    "                    if k in first_dic[a]:\n",
    "                        continue\n",
    "                    num = num + 1\n",
    "        '''\n",
    "        return num\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        dic = defaultdict(set)\n",
    "        for x in ideas:\n",
    "            dic[x[0]].add(x)\n",
    "        ans = 0\n",
    "        cnt = defaultdict(int)\n",
    "        for x in ideas:\n",
    "            for y in ascii_lowercase:\n",
    "                if x[0] == y:\n",
    "                    continue\n",
    "                z = y + x[1:]\n",
    "                if z not in dic[y]:\n",
    "                    cnt[x[0], y] += 1\n",
    "\n",
    "        for (x, y), v in cnt.items():\n",
    "            if (y, x) in cnt:\n",
    "                ans += v * cnt[y, x]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        v = [set() for _ in range(26)]\n",
    "        for id in ideas:\n",
    "            v[ord(id[0]) - ord('a')].add(id)\n",
    "        dp = [[0 for _ in range(26)] for _ in range(26)]\n",
    "        for i in range(26):\n",
    "            for vv in v[i]:\n",
    "                for j in range(26):\n",
    "                    if i == j or not v[j]:\n",
    "                        continue\n",
    "                    newr = chr(ord('a') + j) + vv[1:]\n",
    "                    if newr not in v[j]:\n",
    "                        dp[i][j] += 1\n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                ans += dp[i][j] * dp[j][i]\n",
    "        for i in range(26):\n",
    "            ans -= dp[i][i]\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        ans = 0\n",
    "        pre_a = defaultdict(int)\n",
    "        pre_b = defaultdict(int)\n",
    "        dct = set(ideas)\n",
    "        for word in ideas:\n",
    "            for i in range(26):\n",
    "                w = chr(ord(\"a\")+i)\n",
    "                if w+word[1:] not in dct:\n",
    "                    ans += pre_b[w+word[0]]\n",
    "                    ans += pre_a[w+word[0]]\n",
    "                    \n",
    "            for i in range(26):\n",
    "                w = chr(ord(\"a\")+i)\n",
    "                if w+word[1:] not in dct:\n",
    "                    pre_b[word[0]+w] += 1\n",
    "                    pre_a[word[0]+w] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        ideas = set(ideas)\n",
    "        swap = [[0 for _ in range(26)] for _ in range(26)]\n",
    "        for w in ideas:\n",
    "            v1 = ord(w[0]) - ord('a')\n",
    "            for v2 in range(26):\n",
    "                nw = chr(v2 + ord('a')) + w[1 : ]\n",
    "                if nw not in ideas:\n",
    "                    swap[v1][v2] += 1 \n",
    "        res = 0 \n",
    "        for v1 in range(26):\n",
    "            for v2 in range(26):\n",
    "                res += swap[v1][v2] * swap[v2][v1]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        s = set(ideas)\n",
    "        f = [[0] * 26 for _ in range(26)]\n",
    "        for v in ideas:\n",
    "            i = ord(v[0]) - ord('a')\n",
    "            t = list(v)\n",
    "            for j in range(26):\n",
    "                t[0] = chr(ord('a') + j)\n",
    "                if ''.join(t) not in s:\n",
    "                    f[i][j] += 1\n",
    "        ans = 0\n",
    "        for v in ideas:\n",
    "            i = ord(v[0]) - ord('a')\n",
    "            t = list(v)\n",
    "            for j in range(26):\n",
    "                t[0] = chr(ord('a') + j)\n",
    "                if ''.join(t) not in s:\n",
    "                    ans += f[j][i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        s = set(ideas)\n",
    "        cnt = Counter()\n",
    "        for w in ideas:\n",
    "            for ch in ascii_lowercase:\n",
    "                if ch + w[1:] not in s:\n",
    "                    cnt[ch, w[0]] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for w in ideas:\n",
    "            for ch in ascii_lowercase:\n",
    "                if ch + w[1:] not in s:\n",
    "                    ans += cnt[w[0], ch]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        cnt=collections.defaultdict(list)\n",
    "        for x in ideas:\n",
    "            tail=x[1:]\n",
    "            if tail not in cnt[x[0]]:\n",
    "                cnt[x[0]].append(tail)\n",
    "\n",
    "        ans=0\n",
    "        print(cnt)\n",
    "        for x in cnt:\n",
    "            for y in cnt:\n",
    "                if x==y:\n",
    "                    continue\n",
    "                t=cnt[x]+cnt[y]\n",
    "                lent=len(set(t))\n",
    "                \n",
    "                leny=lent-len(cnt[x])\n",
    "                lenx=lent-len(cnt[y])\n",
    "                ans+=(leny)*lenx\n",
    "\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        ans = 0\n",
    "        suffices = [set() for _ in range(26)]\n",
    "        for idea in ideas: suffices[ord(idea[0]) - 97].add(idea[1:])\n",
    "        for i in range(26):\n",
    "            for j in range(i):\n",
    "                num = sum(suffix in suffices[j] for suffix in suffices[i])\n",
    "                ans += (len(suffices[i]) - num) * (len(suffices[j]) - num)\n",
    "        return ans << 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "\n",
    "        m = collections.defaultdict(set)\n",
    "        for idea in ideas:\n",
    "            m[idea[0]].add(idea[1:])\n",
    "        count = 0\n",
    "        for k1 in m:\n",
    "            for k2 in m:\n",
    "                if k1 == k2:\n",
    "                    continue\n",
    "                ins = 0\n",
    "                for s in m[k1]:\n",
    "                    if s  in m[k2]:\n",
    "                        ins += 1\n",
    "                dis1 = len(m[k1]) - ins\n",
    "                dis2 = len(m[k2]) - ins\n",
    "                count += dis1 * dis2\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            g[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(g.values(), 2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        res = 0\n",
    "        for a, b in combinations(group.values(), 2):\n",
    "            m = len(a & b)\n",
    "            res += (len(a) - m) * (len(b) - m)\n",
    "        return res * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        n = len(ideas)\n",
    "        d = collections.defaultdict(set)\n",
    "        for i in range(n):\n",
    "            d[ideas[i][:1]].add(ideas[i][1:])\n",
    "        ans = 0\n",
    "        for a,b in itertools.combinations(d.values(),2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        # 组合型枚举， 计数每个组首字母i，j的累加值\n",
    "\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(group.values(), 2): # \n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        n = len(ideas)\n",
    "        dic = defaultdict(set)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            dic[ideas[i][0]].add(ideas[i][1:])\n",
    "\n",
    "        for i, j in combinations(dic.values(), 2):\n",
    "            m = len(i & j)\n",
    "\n",
    "            ans += (len(i)- m) * (len(j)-m)\n",
    "\n",
    "        return ans *2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(group.values(), 2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(group.values(), 2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(group.values(), 2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(group.values(), 2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/naming-a-company/\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        # 按照首字母分组\n",
    "        g = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            g[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(g.values(), 2):\n",
    "            common = a & b\n",
    "            ans += (len(a) - len(common)) * (len(b) - len((common)))\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        dd = defaultdict(set)\n",
    "        for i in ideas:\n",
    "            dd[i[:1]].add(i[1:])\n",
    "        keys = sorted(dd.keys())\n",
    "        n = len(keys)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                l, r = dd[keys[i]], dd[keys[j]]\n",
    "                m = len(l & r)\n",
    "                ans += (len(l) - m) * (len(r) - m)\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(group.values(),2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(group.values(), 2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        d = defaultdict(set)\n",
    "        for x in ideas:\n",
    "            d[x[0]].add(x[1:])\n",
    "        # ideas = set(ideas)\n",
    "        ans = 0\n",
    "        for a,b in itertools.product(string.ascii_lowercase, repeat=2):\n",
    "            if a >= b: continue\n",
    "            # p = q = 0\n",
    "            # for x in d[a]:\n",
    "            #     p += (b+x) not in ideas\n",
    "            # for y in d[b]:\n",
    "            #     q += (a+y) not in ideas\n",
    "            p = sum(x not in d[b] for x in d[a])\n",
    "            q = sum(y not in d[a] for y in d[b])\n",
    "            ans += p * q\n",
    "        return 2 * ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        dd = defaultdict(set)\n",
    "        for i in ideas:\n",
    "            dd[i[:1]].add(i[1:])\n",
    "        keys = sorted(dd.keys())\n",
    "        n = len(keys)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                l, r = dd[keys[i]], dd[keys[j]]\n",
    "                ans += len(l - r) * len(r - l) * 2\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for x in ideas:\n",
    "            d[x[0]].append(x[1:])\n",
    "        ideas = set(ideas)\n",
    "        ans = 0\n",
    "        for a,b in itertools.product(string.ascii_lowercase, repeat=2):\n",
    "            if a >= b: continue\n",
    "            p = q = 0\n",
    "            for x in d[a]:\n",
    "                p += (b+x) not in ideas\n",
    "            for y in d[b]:\n",
    "                q += (a+y) not in ideas\n",
    "            ans += p * q\n",
    "        return 2 * ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(set)\n",
    "        for s in ideas:\n",
    "            group[s[0]].add(s[1:])\n",
    "        ans = 0\n",
    "        for a, b in combinations(group.values(), 2):\n",
    "            m = len(a & b)\n",
    "            ans += (len(a) - m) * (len(b) - m)\n",
    "        return ans * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        ideas = list(set(ideas)) \n",
    "        cap = defaultdict(set) \n",
    "        for word in ideas:\n",
    "            cap[word[0]].add(word[1:])\n",
    "        \n",
    "        ans = 0 \n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                if i != j:\n",
    "                    c1, c2 = chr(ord('a') + i), chr(ord('a') + j)\n",
    "                    s = set()\n",
    "                    for x in cap[c1]:\n",
    "                        s.add(x)\n",
    "                    for x in cap[c2]:\n",
    "                        s.add(x) \n",
    "\n",
    "                    ans += (len(s) - len(cap[c1])) * (len(s) - len(cap[c2]))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        ideas = list(set(ideas)) \n",
    "        cap = defaultdict(set) \n",
    "        for word in ideas:\n",
    "            cap[word[0]].add(word[1:])\n",
    "        \n",
    "        ans = 0 \n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                if i != j:\n",
    "                    c1, c2 = chr(ord('a') + i), chr(ord('a') + j)\n",
    "                    s = set()\n",
    "                    for x in cap[c1]:\n",
    "                        s.add(x)\n",
    "                    for x in cap[c2]:\n",
    "                        s.add(x) \n",
    "\n",
    "                    ans += len(s - cap[c1]) * len(s - cap[c2]) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        ordA = ord('a')\n",
    "        suffixMap = defaultdict(int)\n",
    "        for s in ideas:\n",
    "            suffixMap[s[1:]] |= 1<<(ord(s[0]) - ordA)\n",
    "        res = 0\n",
    "        # @cache\n",
    "        def compute(mask1, mask2):\n",
    "            _xor = mask1 ^ mask2\n",
    "            mask1 &= _xor\n",
    "            mask2 &= _xor\n",
    "            return mask1.bit_count()*mask2.bit_count()*2\n",
    "        c = Counter(suffixMap.values())\n",
    "        for mask1, mask2 in combinations(c.keys(), 2):\n",
    "            res += compute(min(mask1, mask2), max(mask1, mask2)) * c[mask1] * c[mask2]\n",
    "            #_xor = mask1 ^ mask2\n",
    "            #mask1 &= _xor\n",
    "            #mask2 &= _xor\n",
    "            #res += mask1.bit_count()*mask2.bit_count()*2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        ordA = ord('a')\n",
    "        suffixMap = defaultdict(int)\n",
    "        for s in ideas:\n",
    "            suffixMap[s[1:]] |= 1<<(ord(s[0]) - ordA)\n",
    "        res = 0\n",
    "        # @cache\n",
    "        def compute(mask1, mask2):\n",
    "            _xor = mask1 ^ mask2\n",
    "            mask1 &= _xor\n",
    "            mask2 &= _xor\n",
    "            return mask1.bit_count()*mask2.bit_count()*2\n",
    "        c = Counter(suffixMap.values())\n",
    "        for mask1, mask2 in combinations(c.keys(), 2):\n",
    "            res += compute(mask1, mask2) * c[mask1] * c[mask2]\n",
    "            #_xor = mask1 ^ mask2\n",
    "            #mask1 &= _xor\n",
    "            #mask2 &= _xor\n",
    "            #res += mask1.bit_count()*mask2.bit_count()*2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        # 初始化一个哈希表来存储每个名字组的首字母的位掩码\n",
    "        group = defaultdict(int)\n",
    "        \n",
    "        # 填充哈希表\n",
    "        for s in ideas:\n",
    "            # 使用位运算将每个名字的首字母添加到相应的名字组的位掩码中\n",
    "            group[s[1:]] |= 1 << (ord(s[0]) - ord('a'))\n",
    "            \n",
    "        # 初始化计数器\n",
    "        ans = 0\n",
    "        \n",
    "        # 初始化一个二维数组来存储每一对首字母的有效名字组合的数量\n",
    "        cnt = [[0] * 26 for _ in range(26)]\n",
    "        \n",
    "        # 计算所有有效的名字组合\n",
    "        for mask in group.values():\n",
    "            for i in range(26):\n",
    "                # 如果位掩码中没有字母 i\n",
    "                if mask >> i & 1 == 0:\n",
    "                    for j in range(26):\n",
    "                        # 如果位掩码中有字母 j\n",
    "                        if mask >> j & 1:\n",
    "                            cnt[i][j] += 1\n",
    "                # 如果位掩码中有字母 i\n",
    "                else:\n",
    "                    for j in range(26):\n",
    "                        # 如果位掩码中没有字母 j\n",
    "                        if mask >> j & 1 == 0:\n",
    "                            ans += cnt[i][j]\n",
    "                            \n",
    "        # 由于每一个有效的名字组合都有两种可能的顺序（A+B 和 B+A）\n",
    "        # 所以最终结果需要乘以 2\n",
    "        return ans * 2\n",
    "\n",
    "# 测试代码\n",
    "s = Solution()\n",
    "print(s.distinctNames([\"coffee\", \"donuts\", \"time\", \"toffee\"]))  # 应输出 6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        res = 0\n",
    "        for idea in ideas:\n",
    "            dic[idea[1:]] |= (1 << ord(idea[0]) - ord('a'))\n",
    "        dp = [[0] * 26 for _ in range(26)]\n",
    "        for v in dic.values():\n",
    "            for i in range(26):\n",
    "                if v & (1 << i):\n",
    "                    for j in range(26):\n",
    "                        if not v & (1 << j):\n",
    "                            dp[i][j] += 1\n",
    "        for i in range(26):\n",
    "            for j in range(i):\n",
    "                res += dp[i][j] * dp[j][i] * 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        d=dict()\n",
    "        for x in ideas:\n",
    "            if x[0] not in d:\n",
    "                d[x[0]]=set()\n",
    "                d[x[0]].add(x[1:])\n",
    "            else:\n",
    "                d[x[0]].add(x[1:])\n",
    "        s=set(ideas)\n",
    "        ans=0\n",
    "        for x in d.keys():\n",
    "            for y in d.keys():\n",
    "                if x!=y:\n",
    "                    ans+=len(d[x]-d[y])*len(d[y]-d[x])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(int)\n",
    "        for s in ideas:\n",
    "            group[s[1:]] |= 1 << (ord(s[0]) - ord('a'))\n",
    "        ans = 0\n",
    "        cnt = [[0] * 26 for _ in range(26)]\n",
    "        for mask in group.values():\n",
    "            for i in range(26):\n",
    "                if mask >> i & 1 == 0:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1:\n",
    "                            cnt[i][j] += 1\n",
    "                else:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1 == 0:\n",
    "                            ans += cnt[i][j]\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group=defaultdict(int)\n",
    "        for s in ideas:\n",
    "            group[s[1:]] |= 1<<(ord(s[0])-ord('a'))\n",
    "        ans=0\n",
    "        cnt=[[0]*26 for _ in range(26)]\n",
    "        for mask in group.values():\n",
    "            for i in range(26):\n",
    "                if mask>>i &1==0:\n",
    "                    for j in range(26):\n",
    "                        if mask >>j &1:\n",
    "                            cnt[i][j]+=1\n",
    "                else:\n",
    "                    for j in range(26):\n",
    "                        if mask >>j &1 ==0:\n",
    "                            ans+=cnt[i][j]\n",
    "        return ans*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group=defaultdict(int)\n",
    "        for s in ideas:\n",
    "            group[s[1:]] |= 1<<(ord(s[0])-ord('a'))\n",
    "        ans=0\n",
    "        cnt=[[0]*26 for _ in range(26)]\n",
    "        for mask in group.values():\n",
    "            for i in range(26):\n",
    "                if mask>>i &1==0:\n",
    "                    for j in range(26):\n",
    "                        if mask >>j &1:\n",
    "                            cnt[i][j]+=1\n",
    "                else:\n",
    "                    for j in range(26):\n",
    "                        if mask >>j &1 ==0:\n",
    "                            ans+=cnt[i][j]\n",
    "        return ans*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(int)\n",
    "        for s in ideas:\n",
    "            group[s[1:]] |= 1 << (ord(s[0]) - ord('a'))\n",
    "        res = 0\n",
    "        cnt = [[0] * 26 for _ in range(26)]\n",
    "        for mask in group.values():\n",
    "            for i in range(26):\n",
    "                if mask >> i & 1 == 0:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1:\n",
    "                            cnt[i][j] += 1\n",
    "\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                res+=cnt[i][j]*cnt[j][i]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        d=dict()\n",
    "        for x in ideas:\n",
    "            if x[0] not in d:\n",
    "                d[x[0]]=set()\n",
    "                d[x[0]].add(x[1:])\n",
    "            else:\n",
    "                d[x[0]].add(x[1:])\n",
    "        s=set(ideas)\n",
    "        ans=0\n",
    "        t=[x for x in d.keys()]\n",
    "        for i in range(len(t)-1):\n",
    "            for j in range(i+1,len(t)):\n",
    "                \n",
    "                ans+=len(d[t[i]]-d[t[j]])*len(d[t[j]]-d[t[i]])\n",
    "        return ans*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(int)\n",
    "        for s in ideas:\n",
    "            group[s[1:]] |= 1 << (ord(s[0]) - ord('a'))\n",
    "        ans = 0\n",
    "        cnt = [[0] * 26 for _ in range(26)]\n",
    "        for mask in group.values():\n",
    "            for i in range(26):\n",
    "                if mask >> i & 1 == 0:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1:\n",
    "                            cnt[i][j] += 1\n",
    "                else:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1 == 0:\n",
    "                            ans += cnt[i][j]\n",
    "        return ans * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(int)\n",
    "        for s in ideas:\n",
    "            group[s[1:]] |= 1 << (ord(s[0]) - ord('a'))\n",
    "        ans = 0\n",
    "        cnt = [[0] * 26 for _ in range(26)]\n",
    "        for mask in group.values():\n",
    "            for i in range(26):\n",
    "                if mask >> i & 1 == 0:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1:\n",
    "                            cnt[i][j] += 1\n",
    "                else:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1 == 0:\n",
    "                            ans += cnt[i][j]\n",
    "        return ans * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(int)\n",
    "        for s in ideas:\n",
    "            group[s[1:]] |= 1 << (ord(s[0]) - ord('a'))\n",
    "        \n",
    "        cnt = [[0] * 26 for _ in range(26)]\n",
    "        ans = 0\n",
    "        for val in group.values():\n",
    "            for i in range(26):\n",
    "                if (val >> i & 1) == 0:\n",
    "                    for j in range(26):\n",
    "                        if (val >> j & 1):\n",
    "                            cnt[i][j] += 1\n",
    "                else:\n",
    "                    for j in range(26):\n",
    "                        if (val >> j & 1) == 0:\n",
    "                            ans += cnt[i][j]\n",
    "        return ans * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        d = defaultdict(set)\n",
    "        for x in ideas:\n",
    "            d[x[0]].add(x[1:])\n",
    "        ideas = set(ideas)\n",
    "        ans = 0\n",
    "        for a,b in itertools.product(string.ascii_lowercase, repeat=2):\n",
    "            if a >= b: continue\n",
    "            p = q = 0\n",
    "            for x in d[a]:\n",
    "                p += (b+x) not in ideas\n",
    "            for y in d[b]:\n",
    "                q += (a+y) not in ideas\n",
    "            # p = sum(x not in d[b] for x in d[a])\n",
    "            # q = sum(y not in d[a] for y in d[b])\n",
    "            ans += p * q\n",
    "        return 2 * ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(int)\n",
    "        size = [0] * 26\n",
    "        bad = [[0] * 26 for _ in range(26)]\n",
    "        for s in ideas:\n",
    "            i = ord(s[0]) - ord('a')\n",
    "            s = s[1:]\n",
    "            mask = group[s]\n",
    "            group[s] |= 1 << i\n",
    "            size[i] += 1\n",
    "            for j in range(26):\n",
    "                if mask >> j & 1:\n",
    "                    bad[i][j] += 1  # 统计 i 无法与多少个 j 开头的字符串交换\n",
    "                    bad[j][i] += 1  # 统计 j 无法与多少个 i 开头的字符串交换\n",
    "        ans = 0\n",
    "        for i, b in enumerate(bad):\n",
    "            for j, m in enumerate(b[:i]):\n",
    "                ans += (size[i] - m) * (size[j] - m)\n",
    "        return ans * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNames(self, ideas: List[str]) -> int:\n",
    "        group = defaultdict(int)\n",
    "        for s in ideas:\n",
    "            # group[X] = 1011001...\n",
    "            group[s[1:]] |= 1 << (ord(s[0]) - ord('a'))\n",
    "        ans = 0\n",
    "        # cnt[25][25]\n",
    "        cnt = [[0] * 26 for _ in range(26)]\n",
    "        for mask in group.values():\n",
    "            for i in range(26):\n",
    "                if mask >> i & 1 == 0:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1:\n",
    "                            # 有j无i\n",
    "                            ans += cnt[i][j]\n",
    "\n",
    "                else:\n",
    "                    for j in range(26):\n",
    "                        if mask >> j & 1 == 0:\n",
    "                            # 有i无j\n",
    "                            cnt[i][j] += 1\n",
    "                            \n",
    "        # 一次遍历，对偶的，所以要乘2\n",
    "        return ans * 2\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/naming-a-company/solutions/1596320/by-endlesscheng-ruz8/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
